/**
 * 树形数据处理工具类
 */

export interface TreeNode<T = any> {
  id: number
  parentId: number | null
  children?: TreeNode<T>[]
  [key: string]: any
}

export interface FlatNode<T = any> {
  id: number
  parentId: number | null
  [key: string]: any
}

/**
 * 将扁平数据转换为树形结构
 * @param flatData 扁平数据数组
 * @param rootParentId 根节点的父ID，默认为 null
 * @returns 树形结构数组
 */
export function buildTree<T extends FlatNode>(
  flatData: T[],
  rootParentId: number | null = null,
): TreeNode<T>[] {
  const tree: TreeNode<T>[] = []
  const map = new Map<number, TreeNode<T>>()

  // 创建映射，为每个节点添加 children 数组
  flatData.forEach((item) => {
    map.set(item.id, { ...item, children: [] })
  })

  // 构建树形结构
  flatData.forEach((item) => {
    if (item.parentId === rootParentId) {
      // 根节点
      tree.push(map.get(item.id)!)
    }
    else {
      // 子节点
      const parent = map.get(item.parentId!)
      if (parent) {
        parent.children!.push(map.get(item.id)!)
      }
    }
  })

  return tree
}

/**
 * 将树形结构转换为扁平数据
 * @param treeData 树形数据数组
 * @returns 扁平数据数组
 */
export function flattenTree<T extends TreeNode>(
  treeData: T[],
): FlatNode<T>[] {
  const result: FlatNode<T>[] = []

  function traverse(nodes: T[], parentId: number | null = null) {
    nodes.forEach((node) => {
      const { children, ...rest } = node
      result.push({ ...rest, parentId } as unknown as FlatNode<T>)

      if (children && children.length > 0) {
        traverse(children as T[], node.id)
      }
    })
  }

  traverse(treeData)
  return result
}

/**
 * 查找树形数据中的节点
 * @param treeData 树形数据数组
 * @param predicate 查找条件函数
 * @returns 找到的节点，未找到返回 undefined
 */
export function findTreeNode<T extends TreeNode>(
  treeData: T[],
  predicate: (node: T) => boolean,
): T | undefined {
  for (const node of treeData) {
    if (predicate(node)) {
      return node
    }

    if (node.children && node.children.length > 0) {
      const found = findTreeNode(node.children as T[], predicate)
      if (found) {
        return found
      }
    }
  }

  return undefined
}

/**
 * 查找树形数据中节点的所有子节点
 * @param treeData 树形数据数组
 * @param nodeId 节点ID
 * @returns 子节点数组
 */
export function getChildrenNodes<T extends TreeNode>(
  treeData: T[],
  nodeId: number,
): T[] {
  const node = findTreeNode(treeData, n => n.id === nodeId)
  return (node?.children || []) as T[]
}

/**
 * 查找树形数据中节点的所有父节点路径
 * @param treeData 树形数据数组
 * @param nodeId 节点ID
 * @returns 父节点路径数组
 */
export function getParentPath<T extends TreeNode>(
  treeData: T[],
  nodeId: number,
): T[] {
  const path: T[] = []

  function findPath(nodes: T[], targetId: number, currentPath: T[]): boolean {
    for (const node of nodes) {
      const newPath = [...currentPath, node]

      if (node.id === targetId) {
        path.push(...newPath)
        return true
      }

      if (node.children && node.children.length > 0) {
        if (findPath(node.children as T[], targetId, newPath)) {
          return true
        }
      }
    }
    return false
  }

  findPath(treeData, nodeId, [])
  return path
}

/**
 * 过滤树形数据
 * @param treeData 树形数据数组
 * @param predicate 过滤条件函数
 * @returns 过滤后的树形数据
 */
export function filterTree<T extends TreeNode>(
  treeData: T[],
  predicate: (node: T) => boolean,
): T[] {
  function filter(nodes: T[]): T[] {
    return nodes
      .filter(predicate)
      .map((node) => {
        const filteredChildren = node.children
          ? filter(node.children as T[])
          : []
        return {
          ...node,
          children: filteredChildren.length > 0 ? filteredChildren : undefined,
        }
      })
      .filter((node) => {
        // 如果节点本身不匹配，但子节点匹配，则保留该节点
        return predicate(node) || (node.children && node.children.length > 0)
      })
  }

  return filter(treeData) as unknown as T[]
}

/**
 * 删除空的 children 属性
 * @param treeData 树形数据数组
 */
export function deleteEmptyChildren<T extends TreeNode>(treeData: T[]): void {
  treeData.forEach((node) => {
    if (node.children && node.children.length === 0) {
      delete node.children
    }
    else if (node.children && node.children.length > 0) {
      deleteEmptyChildren(node.children as T[])
    }
  })
}

/**
 * 计算树形数据的深度
 * @param treeData 树形数据数组
 * @returns 最大深度
 */
export function getTreeDepth<T extends TreeNode>(treeData: T[]): number {
  if (treeData.length === 0)
    return 0

  let maxDepth = 0

  function calculateDepth(nodes: T[], currentDepth: number) {
    nodes.forEach((node) => {
      const depth = currentDepth + 1
      maxDepth = Math.max(maxDepth, depth)

      if (node.children && node.children.length > 0) {
        calculateDepth(node.children as T[], depth)
      }
    })
  }

  calculateDepth(treeData, 0)
  return maxDepth
}

/**
 * 遍历树形数据
 * @param treeData 树形数据数组
 * @param callback 遍历回调函数
 */
export function traverseTree<T extends TreeNode>(
  treeData: T[],
  callback: (node: T, level: number, parent?: T) => void,
): void {
  function traverse(nodes: T[], level: number, parent?: T) {
    nodes.forEach((node) => {
      callback(node, level, parent)

      if (node.children && node.children.length > 0) {
        traverse(node.children as T[], level + 1, node)
      }
    })
  }

  traverse(treeData, 0)
}

/**
 * 根据ID数组获取树形数据中的节点
 * @param treeData 树形数据数组
 * @param ids ID数组
 * @returns 节点数组
 */
export function getNodesByIds<T extends TreeNode>(
  treeData: T[],
  ids: number[],
): T[] {
  const result: T[] = []

  function findNodes(nodes: T[]) {
    nodes.forEach((node) => {
      if (ids.includes(node.id)) {
        result.push(node)
      }

      if (node.children && node.children.length > 0) {
        findNodes(node.children as T[])
      }
    })
  }

  findNodes(treeData)
  return result
}

/**
 * 检查节点是否为叶子节点
 * @param node 树节点
 * @returns 是否为叶子节点
 */
export function isLeafNode<T extends TreeNode>(node: T): boolean {
  return !node.children || node.children.length === 0
}

/**
 * 获取所有叶子节点
 * @param treeData 树形数据数组
 * @returns 叶子节点数组
 */
export function getLeafNodes<T extends TreeNode>(treeData: T[]): T[] {
  const leafNodes: T[] = []

  function findLeafNodes(nodes: T[]) {
    nodes.forEach((node) => {
      if (isLeafNode(node)) {
        leafNodes.push(node)
      }
      else if (node.children && node.children.length > 0) {
        findLeafNodes(node.children as T[])
      }
    })
  }

  findLeafNodes(treeData)
  return leafNodes
}
